package dp;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class leetcode264 {


    public int nthUglyNumber(int n) {
//用堆存储丑数，先把1放入堆，对于在堆中的数字i,那么2*i,3*i,5*i也是丑数
        //当我们往堆放入第i个元素，那么这个数字就是丑数
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int res=0;
        for(int i=1;i<=n;i++){//取出n次，第n次就是第n个丑数
            //将最小数取出，用它去构造新的丑数
            long ugly=heap.poll();
            res=(int)ugly;
            for (int factor : factors) {
                long ne=factor*ugly;
                if(seen.add(ne)) heap.offer(ne);
            }
        }
        return res;
    }


    /**
     * 三指针，nb解法
     * @param n
     * @return
     */
    public int nthUglyNumber1(int n) {
        int[] dp=new int[n+1];
        dp[1]=1;
        int p2=1,p3=1,p5=1;//三个指针都指向第一个元素
        for(int i=2;i<=n;i++){
            int num1=dp[p2]*2;
            int num2=dp[p3]*3;
            int num3=dp[p5]*5;
            dp[i]=Math.min(num1,Math.min(num2,num3));
            if(dp[i]==num1)p2++;
            if(dp[i]==num2)p3++;
            if(dp[i]==num3)p5++;
        }
        return dp[n];
    }
}
